package one.three.web.eleven;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Recent {
	Map<String, Integer> m;

	public Recent() {
		m = new HashMap<String, Integer>();
	}

	public void put(String s) {
		if (m.containsKey(s)) {
			int c = m.get(s);
			m.remove(s, c + 1);
		} else {
			m.put(s, 1);
		}
	}

	public void getK(int kItem) {
		Map<Integer, List<String>> store = new HashMap<Integer, List<String>>();
		int c;
		List<String> l;
		for (String k : m.keySet()) {
			c = m.get(k);
			if (!store.containsKey(c)) {
				l = new ArrayList<String>();
				l.add(k);
				store.put(c, l);
			} else {
				l = store.get(c);
				l.add(k);
			}
		}
		List<Integer> keys = new ArrayList<Integer>();
		for (Integer i : store.keySet()) {
			keys.add(i);
		}
		Collections.sort(keys);
		String[] items = new String[kItem];
		int idx = 0;
		int ki = keys.size() - 1;
		List<String> e;
		while (idx < kItem) {
			e = store.get(keys.get(ki));
			for (int i = 0; i < e.size(); i++) {
				if (idx + i >= kItem) {
					break;
				}
				items[idx + i] = e.get(i);
			}
			idx += e.size();
			ki--;
		}

		System.out.println(Arrays.toString(items));
	}

	public static void main(String[] args) {
		Recent r = new Recent();
		r.put("jim");
		r.put("jim");
		r.put("tom");
		r.put("tom");
		r.put("tom");
		r.put("smith");
		r.put("smith");

		r.getK(3);
	}
}
